/*
 * Author: Alberto De Pena
 * Applied Algorithms
 * pancakes.cpp
*/
#include <iostream>
#include <string>
#include <fstream>
#include <set>
#include <queue>
using namespace std;

struct PancakeStack
{
    string arrangement;
    int flips;

    bool operator<(const PancakeStack& other) const
    {
        size_t otherLength = other.arrangement.length();
        size_t length = arrangement.length();
        int offset = 0;

        while(true)
        {
            if(offset == length || offset == otherLength)
            {
                if(length == otherLength)
                    return false;
                else if(length > otherLength)
                    return false;
                else
                    return true;
            }
            else if((int)arrangement[offset] < (int)other.arrangement[offset])
                return true;
            else if((int)arrangement[offset] > (int)other.arrangement[offset])
                return false;
            else
                ++offset;
        }
    }
};

PancakeStack initial;
set<PancakeStack> MarkedArrangements;

bool isSolution(const string& arrangement)
{
    size_t length = arrangement.length();

    for(unsigned int i = 0; i < length; i++)
    {
        //last character in the string
        if(i + 1 == length)
        {
            if((int)arrangement[i] < 95)
                return true;
            else
                return false;
        }
        //not the last character in the string
        else
        {
            if((int)arrangement[i] < 95 && (int)arrangement[i+1] < 95 && (int)arrangement[i] <= (int)arrangement[i+1])
            {
                //do nothing, just let it increment
            }
            else
                return false;
        }
    }
    return true;
}

string FlipStack(const string& arrangement, const unsigned int amountToFlip)
{
    string firstPart = "", secondPart = "";

    size_t length = arrangement.length();
    unsigned int dontFlip = length - amountToFlip;

    for(unsigned int i = 0; i < dontFlip; i++)
        firstPart += arrangement[i];

    for(unsigned int i = 0; i < amountToFlip; i++)
        secondPart += arrangement[i + dontFlip];

    size_t secondLength = secondPart.length();

    if(secondLength > 0)
    {
        if(secondLength == 1)
        {
            if((int)secondPart[0] < 95)
                secondPart[0] = tolower(secondPart[0]);
            else
                secondPart[0] = toupper(secondPart[0]);
        }
        else
        {
            //flip to opposite case
            for(unsigned int i = 0; i < secondLength; i++)
            {
                if((int)secondPart[i] < 95)
                    secondPart[i] = tolower(secondPart[i]);
                else
                    secondPart[i] = toupper(secondPart[i]);
            }

            //swap spots
            for(unsigned int j = 0; j < secondLength/2; j++)
            {
                char temp = secondPart[j];
                secondPart[j] = secondPart[secondLength - 1 - j];
                secondPart[secondLength - 1 - j] = temp;
            }
        }
    }

    return firstPart + secondPart;
}

int FindSolution()
{
    PancakeStack final, cur, differentStack;
    queue<PancakeStack> PossibleStacks;
    final.flips = 0;
    
    cur.flips = 0;
    cur.arrangement = initial.arrangement;

    if(isSolution(cur.arrangement))
        final = cur;
    else
    {
        size_t length = cur.arrangement.length();
        MarkedArrangements.insert(cur);
        for(unsigned int i = 1; i <= length; i++)
        {
            differentStack.arrangement = FlipStack(cur.arrangement, i);
            differentStack.flips = cur.flips + 1;
            if(!MarkedArrangements.count(differentStack))
            {
                MarkedArrangements.insert(differentStack);
                PossibleStacks.push(differentStack);
            }
        }

        bool solutionFound = false;

        while(solutionFound == false && !PossibleStacks.empty())
        {
            cur = PossibleStacks.front();
            PossibleStacks.pop();
            if(isSolution(cur.arrangement))
            {
                solutionFound = true;
                final = cur;
            }
            else
            {
                for(unsigned int i = 1; i <= length; i++)
                {
                    differentStack = cur;
                    differentStack.arrangement = FlipStack(cur.arrangement, i);
                    differentStack.flips = cur.flips + 1;
                    if(!MarkedArrangements.count(differentStack))
                    {
                        MarkedArrangements.insert(differentStack);
                        PossibleStacks.push(differentStack);
                    }
                }
            }
        }

    }

    MarkedArrangements.clear();
    while(!PossibleStacks.empty())
        PossibleStacks.pop();

    return final.flips;
}

void main()
{
    ifstream fin;
    ofstream fout;

    fin.open("pancakes.in");
    fout.open("pancakes.out");

    getline(fin, initial.arrangement);
    while(initial.arrangement != "0")
    {
        fout << FindSolution() << endl;
        getline(fin, initial.arrangement);
    }

    fin.close();
    fout.close();
}

